#ifndef SIMPLE_SUPPORT_ALGORITHM_SEARCH_HPP
#define SIMPLE_SUPPORT_ALGORITHM_SEARCH_HPP

#include "mismatch.hpp" // mismatch
#include "../range.hpp" // range

namespace simple::support
{

	// cause we don't get a proper standard search until c++20, and even then it depends on super experimental ranges library
	// (how does stuff like that even get in i wonder -_-)
	template <typename It, typename NeedleIt>
	[[nodiscard]] constexpr
	range<It> search(It begin, It end, NeedleIt nbegin, NeedleIt nend)
	{
		while(true)
		{
			auto [found_end, match_end] = support::mismatch(begin, end, nbegin, nend);
			if(match_end == nend)
				return {begin, found_end};
			else if(found_end == end)
				return {end, end};
			++begin;
		}
		return {end,end}; // unreachable
	}

	// TODO: nearly identical to searche above
	template <typename It, typename NeedleIt>
	[[nodiscard]] constexpr
	std::pair<range<It>, NeedleIt> search_prefix(It begin, It end, NeedleIt nbegin, NeedleIt nend)
	{
		while(true)
		{
			auto [found_end, match_end] = support::mismatch(begin, end, nbegin, nend);
			if(match_end != nbegin) // we want any size match
				return {{begin, found_end}, match_end};
			else if(found_end == end)
				return {{end, end}, nbegin};
			++begin;
		}
		return {{end,end}, nend}; // unreachable
	}

	// TODO: nearly identical to search above
	template <typename It, typename NeedleIt>
	[[nodiscard]] constexpr
	range<It> search(It begin, It end, NeedleIt nbegin) // assuming infinite needle
	{
		while(true)
		{
			auto [found_end, match_end] = support::mismatch(begin, end, nbegin);
			if(match_end != nbegin) // we can't ever find all of it so we make due with some
				return {begin, found_end};
			else if(found_end == end)
				return {end, end};
			++begin;
		}
		return {end,end}; // unreachable
	}


} // namespace simple::support

#endif /* end of include guard */
